1. Field of the Invention
The present invention relates to a digital signature, and more particularly, to a method and an apparatus for generating and verifying a digital signature, which rapidly generates a digital signature by simplifying a signing procedure.
2. Description of the Related Art
A digital signature is information to identify a signer's identity through a computer to replace writing materials such as pen and pencils. Such a digital signature is appended to a message or is logically combined with electronic data. The digital signature is used for the purpose of identifying a signer's identity and certifying authentication of a person with a corresponding message. The digital signature is an electronic substitute for a manual signature or seal, and may be information generated through a computer instead of a pen. In general, the digital signature uses a public key (asymmetrical) ciphering system.
The digital signature certifies a fact that a person indicated as a writer in the digital signature writes a corresponding electronic document, and a fact that written contents were not forged or altered during transmission and reception. Further, the digital signature prevents a signer from denying the writing or signing of an electronic document.
The digital signature may effectively reduce the occurrence of a danger such as a loss of information when performing Internet shopping or cyber banking transactions. Accordingly, a use of the digital signature may deter peculation or forgery of private information.
The digital signature has been used for banking transactions such as Internet banking, Internet civil service, and Internet shopping, and has been expanding in scope to be used in International electronic commercial transactions and electronic voting. Certified authentication notes, necessary in Internet banking or on-line stock trading, is a representative digital signature issued by a national public authentication center and a public key thereof is managed thereby.
Several schemes exist, including the Rivest, Shamir, and Adelman (referred to as ‘RSA’ hereinafter) scheme and the McEliece scheme, for generating a digital signature using a public key. The RSA scheme is an algorithm developed in 1997 by three mathematicians Ron Rivest, Adi Shamir, and Leonard Adelman, and has been utilized in Internet encryption and authentication systems. The RSA scheme uses two large prime numbers (equal to or greater than 140). A public key and a private key are produced from a product of the two prime numbers and an additional calculation. The RSA scheme can encrypt and decrypt Internet information, and, more particularly, electronic mail. However, the RSA scheme has a drawback in that the functional operation of the scheme is complex.
FIG. 1 is a flow chart showing a conventional method for generating and transmitting a digital signal for a message to a receiver side using the McEliece scheme. Hereinafter, a conventional method for transmitting a generated digital signature by reference to FIG. 1. When explaining the conventional method, the part of generating the digital signal is referred to as ‘digital signature generator’, and the part of receiving the digital signal is referred to as ‘digital signature receiver’.
In step S100, a digital signature generator generates a digital message m to be signed. In step S102, the digital signature generator calculates a hash function for the message m to be signed using a hash algorithm. A Secure Hash Algorithm (referred to as ‘SHA’ hereinafter) may be used in step S102, which is a kind of hash algorithms. The SHA is an algorithm specified in the Secure Hash Standard (SHS), which was developed by National Institute of Standards and Technology (NIST) in U.S.A. The SHA converts a message having a length of 264 bits or less into a reduced message having a length of 160 bits. Since the SHA is a kind of hash algorithm, it is a one-way algorithm. Since the SHA is not related to the present invention, a detailed description thereof is omitted. In step S102, the digital signature generator sets “m′” as SHA(m).
In step S104, the digital signature generator outputs “H−1 m′”. “H” is a parity check matrix, which is a type of public key. Additionally, besides the digital signature generator and the digital receiver, the third party may also acquire “H”. However, due to characteristics of “H”, only persons knowing a construction of “H”, can acquire “H−1”, which is an inverse matrix of “H”. Consequently, the digital signature generator knowing a construction of “H”, can also acquire “H−1”.
In step S106, the digital signature generator judges whether or not the acquired “H−1m′” is a code word having the desired weight value. The weight value means the number of “1” in a code word, which is composed of “0” and “1”. Accordingly, when the desired weight value is “3”, the digital signature generator judges whether or not the number of “1s” in the generated code word is three. When the generated “H−1 m′” is a code word having the desired weight value, a routine goes to step S110. On the contrary, when the generated “H−1 m′” is not the code word having the desired weight value, a routine goes to step S108.
In step S108, the digital signature generator transforms “m” in a set fashion. As an example, by adding “1” to a transmitted message, “m” can be transformed. That is, when “m” is “1001100”, a transformed “m” is “1001101”. In step S108, “mT” can be set as “m”. After the routine returns to step S102, the digital signature generator calculates a hash function for “m”. Although it is shown in step S102 that the hash function for “m” is calculated, a hash function for a transformed message is calculated when the transmitted message is transformed.
In step S110, the digital signature generator generates a digital signature (a), which is “H−1 m′”. In step S112, the digital signature generator transfers “m” together with the generated “a” to a digital signature receiver.
As noted previously, when “H−1 m′” generated in step S104 is a code word having a desired weight value, the computation amount of the digital signature generator is reduced. However, there is a rare probability that “H−1 m′” generated by the digital signature generator is a code word having a desired weight value. Steps S102 to S108 should repeat until the digital signature generator acquires a code word having a desired weight value. However, repeating the steps S102 to S108 increases the number of computations. Accordingly, a method capable of reducing the number of computations required to generate the digital signature by the digital signature generator, is needed.